#include <cmath>
#include <cstddef>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lesshead,*greaterhead,*lesstail,*greatertail;
        lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));

        struct ListNode* cur = pHead;
        while(cur)
        {
            if(cur->val <x)
            {
                lesstail->next = cur;
                lesstail = cur;
            }else {
                greatertail->next = cur;
                greatertail = cur;
            }

            cur = cur->next;
        }
        lesstail->next = greaterhead->next;

        greatertail->next = nullptr;
        struct ListNode* head = lesshead->next;
        free(lesshead);
        free(greaterhead);

        return head;
    }
};

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA,*curB;
    curA = headA;
    curB = headB;
    int len1 = 1;
    int len2 = 1;
    while(curA->next)
    {
        ++len1;
        curA = curA->next;
    }
    while(curB->next)
    {
        ++len2;
        curB = curB->next;
    }
    if(curB != curA)
        return NULL;

    struct ListNode* longhead = headA;
    struct ListNode* shorthead = headB;
    int gap = abs(len1-len2);
    if(len2>len1)
    {
        longhead = headB;
        shorthead = headA;
    }

    while(gap--)
    {
       longhead = longhead->next;
    }

    while(longhead != shorthead)
    {
        longhead = longhead->next;
        shorthead = shorthead->next;
    }

    return longhead;
}


bool hasCycle(struct ListNode *head) {
    struct ListNode* slow =head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

        if(fast == slow)
            return true;
    }

    return false;
}
